"""
 你和你的朋友，两个人一起玩Nim 游戏：
 桌子上有一堆石头。
 你们轮流进行自己的回合，你作为先手。
 每一回合，轮到的人拿掉1 - 3 块石头。
 拿掉最后一块石头的人就是获胜者。
 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false
 example 1:
     输入: n = 4
     输出: false

 example 2:
     输入: n = 1
     输出: true

 example 3:
     输入: n = 2
     输出: true
"""


# 博弈论
# Nim游戏，只要数字总数n，能取得的最小值a和能取得的最大值b加起来的和c有如下关系: n % c == 0 先手必输，前提是可选的数字要是连续的
# 否则，先手只要抢到余数就必胜。
# 原因很简单，c相当于每次游戏先手可以控制的两人走的最近的一步，就是说，每次两个人报数，是两个数字，
# 不管对方选择了范围内哪个数字，都可以在第二次报数的时候，把两个人报的数字和凑成c。
# 比如如果是1，2，3，不管对面报几，你都可以选另一个数字，把总和凑成4。
# 比如如果是1，2，3，4，不管对面报几，你都可以选另一个数字，把总和凑成5。
# 所以只要先手抢到了余数，那么剩下的每一轮，先手都可以保证整体前进c

# 如果是不连续的，例如：1，2，4，对面报了2，就凑不到5了。就要分成几个情况讨论了
def can_win_nim(n: int) -> bool:
    return n % 4 != 0


if __name__ == '__main__':
    print(can_win_nim(4))
    print(can_win_nim(1))
    print(can_win_nim(2))